package leetcode.editor.cn.q1_300.q100;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 由下往上 会更快
 *
 * @author qidi
 * @date 2022-01-07 16:03:52
 */
class Q0120_Triangle {

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int minimumTotal(List<List<Integer>> triangle) {
            int m = triangle.size();
            if (m == 1) return triangle.get(0).get(0);

            int n = triangle.get(m - 1).size();

            int[] dp = triangle.get(m - 1).stream().mapToInt(Integer::valueOf).toArray();
            for (int i = m - 2; i >= 0; i--) {
                for (int j = 0; j <= i; j++) {
                    dp[j] = Math.min(dp[j], dp[j + 1]) + triangle.get(i).get(j);
                }
            }

            return dp[0];
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)


    public static void main(String[] args) {
        Solution solution = new Q0120_Triangle().new Solution();
        List<List<Integer>> a = new ArrayList<>();
        a.add(Arrays.asList(2));
        a.add(Arrays.asList(3, 4));
        a.add(Arrays.asList(6, 5, 7));
        a.add(Arrays.asList(4, 1, 8, 3));
        solution.minimumTotal(a);
    }
}